﻿#include <iostream>

#define MAX(a,b) (a>b?a:b)

static int longestLengthOfSubSequence(const char* str)
{
	if (!str) return 0;

	auto strLen = strlen(str);
	if (strLen <= 1) return strLen;
	if (strLen == 2) return str[0] == str[1] ? 2 : 1;

	int* dp = (int*)malloc(strLen * strLen * sizeof(int));
	memset(dp, 0, strLen * strLen * sizeof(int));
	for (int i = 0; i < strLen; i++)
	{
		dp[i + i * strLen] = 1;
		if (i + 1 < strLen)
		{
			dp[i + 1 + i * strLen] = str[i] == str[i + 1] ? 2 : 1;
		}
	}

	int left;
	int down;
	int leftDown;
	for (int i = strLen - 1 - 2; i >= 0; i--)
	{
		for (int j = i + 2; j < strLen; j++)
		{
			left = dp[j - 1 + i * strLen];
			down = dp[j + (i + 1) * strLen];
			leftDown = dp[j - 1 + (i + 1) * strLen];
			if (str[i] == str[j])
			{
				leftDown += 2;
			}

			dp[j + i * strLen] = MAX(leftDown, MAX(left, down));
		}
	}

	for (int i = 0; i < strLen; i++)
	{
		for (int j = 0; j < strLen; j++)
		{
			printf("%d ", dp[j + i * strLen]);
		}

		printf("\n");
	}

	int res = dp[strLen - 1];
	free(dp);
	return res;
}

/**
 * 给定一个字符串，求最长的回文子序列。注意区分子序列和子串的不同。
 * 
 * 思路：
 * 动态规划的范围尝试方法。从位置i到位置j的最长回文子序列
 * 分为4种情况
 * 1. 最长回文子序列不以i结尾，不以j结尾，看(i+1,j-1)
 * 2. 最长回文子序列以i结尾，但是不以j结尾, 看(i,j-1) 
 * 3. 最长回文子序列不以i结尾，但是以j结尾, 看(i+1,j)
 * 4. 当且仅当i和j字符相同时，最长回文子序列以i结尾，以j结尾, (i+1,j-1)+2
 * 
 * 举例:
 * str="112ab3cd2e1"
 * 
 *         1   1   2   a   b   3   c   d   2   e   1
 *         0   1   2   3   4   5   6   7   8   9  10   j
 * -------------------------------------------------------
 *  1   0| 1   2   2   2   2   2   2   2   2   2   5
 *  1   1| X   1   1   1   1   1   1   1   3   3   3
 *  2   2| X   X   1   1   1   1   1   1   3   3   3
 *  a   3| X   X   X   1   1   1   1   1   1   1   1
 *  b   4| X   X   X   X   1   1   1   1   1   1   1
 *  3   5| X   X   X   X   X   1   1   1   1   1   1
 *  c   6| X   X   X   X   X   X   1   1   1   1   1
 *  d   7| X   X   X   X   X   X   X   1   1   1   1
 *  2   8| X   X   X   X   X   X   X   X   1   1   1
 *  e   9| X   X   X   X   X   X   X   X   X   1   1
 *  1  10| X   X   X   X   X   X   X   X   X   X   1
 *      i|
 * 
 * ∵i≤j，∴45°斜线以下的格子，都没有意义。
 * i==j时，由于只有一个字符，故填1.
 * i+1==j时，相比较i==j的情况，只是多了一个字符，所以，如果这两个字符相同，则填2；不同则填1.
 * 
 * 对于普遍位置i和j, 则根据上文提到的4种情况，(i,j)格子的值由左边的格子，下边的格子和左下的格子决定，故可以从(8,10)开始往上填写：
 * (8,10)->(7,9)->(7,10)->(6,8)->(6,9)->(6,10)->(5,7)->(5,8)->(5,9)->(5,10)->...->(0,10)
 */
int main_longestLengthOfPalindromicSubSequence()
{
	char str[] = "w13r1r13w";
	auto max = longestLengthOfSubSequence(str);
	printf("%d", max);
	return 0;
}